#ifndef _GRID_SRC_H_
#define _GRID_SRC_H_

#include <iostream>
#include <utility>
#include <cmath>
#include <vector>
#include <iterator>
#include <list>
#include <cmath>
#include <sstream>
#include <map>
#include <numeric>

#include "grid.h"
//#include "cell.h"
#include "line.h"


#define EPSILON 0.0000000001

template <class Cell, class Inserter>
grid_t<Cell, Inserter>::grid_t() : cell_size_(.0), min_idx_(cell_idx_t(0, 0)), max_idx_(cell_idx_t(0, 0))
    , default_cell_(Cell()) {}


template <class Cell, class Inserter>
grid_t<Cell, Inserter>::grid_t(double cell_size) : cell_size_((int)cell_size), min_idx_(cell_idx_t(0, 0))
    , max_idx_(cell_idx_t(0, 0)), default_cell_(Cell()) {}


template <class Cell, class Inserter>
grid_t<Cell, Inserter>::grid_t(polygon_t const & polygon, double cell_size)
    : cell_size_(cell_size), default_cell_(Cell())
{
    cell_idx_t idx_0 = cell_idx(polygon[0][0]);
    min_idx_ = cell_idx_t(idx_0.first, idx_0.second);
    max_idx_ = cell_idx_t(idx_0.first, idx_0.second);
    for(size_t i = 0; i < polygon.size(); ++i)
    {
        Inserter inserter;
        boost::function<void (Cell &, segment_t const &)> f = boost::ref(inserter);
        for(size_t j = 0; j < polygon[i].size() - 1; ++j)
        {
            visit(polygon[i][j], polygon[i][j + 1], f);
        }
        visit(polygon[i][polygon[i].size() - 1], polygon[i][0], f);
    }
    validate();
}


template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::visit(point_t const & begin, point_t const & end, boost::function<void (Cell &, segment_t const &)> processor)
{
    if (min_idx_ == max_idx_)
		min_idx_ = cell_idx(begin); 
	
	cell_visiter_t visiter(processor, segment_t(begin, end), this);
    line_t segment_line(begin, end);
    cell_idx_t cell = cell_idx(visiter.segment().first);
    if(segment_line.is_vertical() || segment_line.is_horizontal())
    {
        if(segment_line.is_horizontal()){
            cell_hor_diapason(cell_idx(visiter.segment().first)
                    , cell_idx(visiter.segment().second), visiter);
        }
		else
		{
            cell_vert_diapason(cell_idx(visiter.segment().first)
                    , cell_idx(visiter.segment().second), visiter);
        }
    }
    else
    {
        visiter(cell);
        cell_idx_t next;
        while (process(cell, visiter, next))
        {
            cell = next;
        }
    }
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::visit(segment_t const & segment, boost::function<void (Cell &, segment_t const &)> processor)
{
    visit(segment.first, segment.second, processor);
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::visit(contour_t const & contour, boost::function<void (Cell &, segment_t const &)> processor)
{
    for(size_t i = 1; i < contour.size(); ++i)
    {
        visit(contour[i - 1], contour[i], processor);
    }
    visit(contour[contour.size() - 1], contour[0], processor);
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::visit(polygon_t const & polygon, boost::function<void (Cell &, segment_t const &)> processor)
{
    for(size_t i = 0; i < polygon.size(); ++i)
    {
        visit(polygon[i], processor);
    }
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::validate()
{
	add_empty_cells();
    set_centers_states();
}

template <class Cell, class Inserter>
size_t grid_t<Cell, Inserter>::size() const
{
    size_t dx = max_idx_.first - min_idx_.first + 1;
    size_t dy = max_idx_.second - min_idx_.second + 1;
    return dx * dy;
}

template <class Cell, class Inserter>
size_t grid_t<Cell, Inserter>::width() const
{
    size_t dx = max_idx_.first - min_idx_.first + 1;
    return dx;
}

template <class Cell, class Inserter>
Cell & grid_t<Cell, Inserter>::operator [] (size_t idx)
{
    size_t dx = max_idx_.first - min_idx_.first + 1;
    int i = idx % dx + min_idx_.first;
    int j = idx / dx + min_idx_.second;
    stdext::hash_map<cell_idx_t, Cell, cell_idx_hash>::iterator iter;
    iter = data_.find(cell_idx_t(i, j));
    if(iter != data_.end())
        return iter->second;
    return default_cell_;
}

template <class Cell, class Inserter>
Cell const & grid_t<Cell, Inserter>::operator [] (size_t idx) const
{
    size_t dx = max_idx_.first - min_idx_.first + 1;
    int i = idx % dx + min_idx_.first;
    int j = idx / dx + min_idx_.second;
    stdext::hash_map<cell_idx_t, Cell, cell_idx_hash>::const_iterator iter;
    iter = data_.find(cell_idx_t(i, j));
    if(iter != data_.end())
        return iter->second;
    return default_cell_;
}

template <class Cell, class Inserter>
Cell const & grid_t<Cell, Inserter>::cell_at(point_t const & point) const
{
    cell_idx_t idx = cell_idx(point);
    stdext::hash_map<cell_idx_t, Cell, cell_idx_hash>::const_iterator iter = data_.find(idx);
    if(iter != data_.end())
        return iter->second;
    return default_cell_;
}

template <class Cell, class Inserter>
double grid_t<Cell, Inserter>::cell_size() const
{
    return cell_size_;
}

template <class Cell, class Inserter>
bool grid_t<Cell, Inserter>::inside(point_t const & point) const
{
    Cell cell = cell_at(point);
    manhattan_line_t m_line(point, cell.center());
	
	boost::optional<segment_t const &> seg = cell.min_segment(m_line, VERT_PART);
	point_pos pos_a = (seg) ? point_position(*seg, point) : UNDEFINED;
    
	seg = cell.min_segment(m_line, HOR_PART);
	point_pos pos_b = (seg) ? point_position(*seg, m_line.corner()) : UNDEFINED;
    point_pos pos_c = (cell.center_in()) ? LEFT : RIGHT;

    bool corner_pos = false;
    if( (pos_b == pos_c && pos_b != ON) || pos_b == UNDEFINED)
        corner_pos = cell.center_in();
    else corner_pos = (pos_b == LEFT || pos_b == ON);

    if( (pos_a == pos_b && pos_a != ON) || pos_a == UNDEFINED)
        return corner_pos;
    return (pos_a == LEFT || pos_a == ON);
}

template <class Cell, class Inserter>
std::ostream & operator<< (std::ostream & out, grid_t<Cell, Inserter> const & grid)
{
    out << grid.cell_size_ << std::endl;
    stdext::hash_map<cell_idx_t, Cell, grid_t<>::cell_idx_hash>::const_iterator i = grid.data_.begin();
    for(; i != grid.data_.end(); ++i)
    {
        if(!i->second.empty())
        {
            out << "_ " << i->first.first << "; " << i->first.second << " | ";
            out << i->second << std::endl;
        }
    }
    return out;
}

template <class Cell, class Inserter>
std::istream & operator>> (std::istream & in, grid_t<Cell, Inserter> & grid)
{
    grid = grid_t<Cell, Inserter>();
    std::string buf;
    std::getline(in, buf);
    std::stringstream ss_size(buf);

    if(ss_size >> grid.cell_size_) {
        buf.clear();
    
        std::copy(std::istreambuf_iterator<char>(in), std::istreambuf_iterator<char>(),
              std::back_inserter(buf));
        std::stringstream ss(buf);
        cell_idx_t idx;
        char delim1, delim2, delim3;
        Cell cell;
    
        size_t i = 0;
        while(ss >> delim1 >> idx.first >> delim2 >> idx.second >> delim3 >> cell)
        {
            if(delim1 != '_' || delim2 != ';' || delim3 != '|') break;

            grid.data_.insert(std::make_pair(idx, cell));
            
            if(i > 1)
            {
                grid.check_grid_corners(idx);
            }
            else if((i++) == 0)
            {
                grid.min_idx_ = grid.max_idx_ = idx;
            }
        }
    }
    if(grid.cell_size_ == 0)
    {
        grid = grid_t<Cell, Inserter>();
    } else
    {
        grid.add_empty_cells();
    }
    return in;
}

template <class Cell, class Inserter>
cell_idx_t grid_t<Cell, Inserter>::cell_idx(point_t const & point) const
{
    int idx_i = (int)(point.x + cell_size_/2.0) / (cell_size_);
    if(idx_i < 0) --idx_i;
    int idx_j = (int)(point.y + cell_size_/2.0) / (cell_size_);
    if(idx_j < 0) --idx_j;
    return cell_idx_t(idx_i, idx_j);
}

template <class Cell, class Inserter>
point_t grid_t<Cell, Inserter>::cell_center(cell_idx_t const & idx) const
{
    double x = idx.first * cell_size_;
    double y = idx.second * cell_size_;
    return point_t(x, y);
}

template <class Cell, class Inserter>
segment_t grid_t<Cell, Inserter>::get_border(border_t border_num, cell_idx_t const & idx) const
{
    point_t center = cell_center(idx);
    if(border_num == RIGHT_B)
        return segment_t(point_t(center.x + cell_size_/2, center.y - cell_size_/2),
                         point_t(center.x + cell_size_/2, center.y + cell_size_/2) );
    if(border_num == LEFT_B)
        return segment_t(point_t(center.x - cell_size_/2, center.y + cell_size_/2),
                         point_t(center.x - cell_size_/2, center.y - cell_size_/2) );
    if(border_num == TOP_B)
        return segment_t(point_t(center.x - cell_size_/2, center.y - cell_size_/2),
                         point_t(center.x + cell_size_/2, center.y - cell_size_/2) );
    if(border_num == BOTTOM_B)
        return segment_t(point_t(center.x + cell_size_/2, center.y + cell_size_/2),
                         point_t(center.x - cell_size_/2, center.y + cell_size_/2) );
    return segment_t(point_t(0, 0), point_t(0, 0));
}

///cell_idx_hash
template <class Cell, class Inserter>
int grid_t<Cell, Inserter>::cell_idx_hash::operator() (cell_idx_t const & idx) const
{
    return (idx.first + idx.second * idx.first);
}

template <class Cell, class Inserter>
bool grid_t<Cell, Inserter>::cell_idx_hash::operator() (cell_idx_t const & l, cell_idx_t const & r) const
{
	if(l.first == r.first)
		return (l.second < r.second);
	return (l.first < r.first); 
}


template <class Cell, class Inserter>
cell_idx_t grid_t<Cell, Inserter>::cell_vert_diapason(cell_idx_t const & begin,
                                   cell_idx_t const & end, cell_visiter_t & visiter) const
{
    int max_y = (std::max)(begin.second, end.second);
    int min_y = (std::min)(begin.second, end.second);
    for(int j = min_y; j <= max_y; ++j)
    {
        visiter(cell_idx_t(begin.first, j));
    }
    return cell_idx_t(begin.first, min_y);
}

template <class Cell, class Inserter>
cell_idx_t grid_t<Cell, Inserter>::cell_hor_diapason(cell_idx_t const & begin,
                                    cell_idx_t const & end, cell_visiter_t & visiter) const
{
    int max_x = (std::max)(begin.first, end.first);
    int min_x = (std::min)(begin.first, end.first);
    for(int j = min_x; j <= max_x; ++j)
    {
        cell_idx_t cell(j, begin.second);
        visiter(cell);
    }
    return cell_idx_t(min_x, begin.second);
}

template <class Cell, class Inserter>
bool grid_t<Cell, Inserter>::process(cell_idx_t const & last
	, cell_visiter_t & visiter, cell_idx_t & next)
{
    segment_t border;
    if (visiter.step() < 0)
    {
        border = get_border(LEFT_B, last);
    }
    else{
        border = get_border(RIGHT_B, last);
    }
    line_t border_line(border.first, border.second);
    point_t point;
    point_t begin = visiter.start_point();
    if(intersects(visiter.line(), border_line, point))
    {
        if(!visiter.move_start_point(point.x))
        {
            cell_vert_diapason(cell_idx(begin), cell_idx(visiter.segment().second), visiter);
        }
        else
        {
            cell_idx_t point_cell = cell_vert_diapason(cell_idx(begin), cell_idx(point), visiter);
            point_cell.first += visiter.step();
            visiter(point_cell);
            next = point_cell;
            return true;       
        }
    }
    return false;
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::check_grid_corners(cell_idx_t const & idx)
{
    if(idx.first < min_idx_.first)
    {
        min_idx_.first = idx.first;
    }
    if(idx.second < min_idx_.second)
    {
        min_idx_.second = idx.second;
    }
    if(idx.first > max_idx_.first)
    {
        max_idx_.first = idx.first;
    }
    if(idx.second > max_idx_.second)
    {
        max_idx_.second = idx.second;
    }
}

template <class Cell, class Inserter>
bool operator== (grid_t<Cell, Inserter> const & left, grid_t<Cell, Inserter> const & right)
{
    if(left.size() != right.size())
        return false;
    for(size_t i = 0; i < left.size(); ++i)
    {
        if(left[i] != right[i] && !left[i].empty() && !right[i].empty())
            return false;
    }
    return true;
}

template <class Cell, class Inserter>
bool operator!= (grid_t<Cell, Inserter> const & left, grid_t<Cell, Inserter> const & right)
{
    return !(left == right);
}


template <class Cell, class Inserter>
grid_t<Cell, Inserter>::cell_visiter_t::cell_visiter_t
    (boost::function<void (Cell &, segment_t const &)> processor, segment_t const & segment
	, grid_t<Cell, Inserter> * grid)
: processor_(processor), segment_(segment), grid_(grid), segment_turned_(false)
{
    if(segment_.first.y < segment_.second.y)
    {
        std::swap(segment_.first, segment_.second);
        segment_turned_ = true;
    }
    start_point_ = segment_.first;
    step_ = (segment_.first.x > segment_.second.x) ? -1: 1;
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::cell_visiter_t::operator() (cell_idx_t const & idx)
{
    if(grid_->data_.find(idx) == grid_->data_.end())
    {
        Cell new_cell(grid_->cell_center(idx));
        grid_->check_grid_corners(idx);
        grid_->data_.insert(std::make_pair(idx, new_cell));
    }
    segment_t seg = (segment_turned_) ? segment_t(segment_.second, segment_.first) : segment_;
    processor_(grid_->data_[idx], seg);
}

template <class Cell, class Inserter>
segment_t const & grid_t<Cell, Inserter>::cell_visiter_t::segment() const
{
    return segment_;
}

template <class Cell, class Inserter>
line_t grid_t<Cell, Inserter>::cell_visiter_t::line() const
{
    return line_t(segment_.first, segment_.second);
}

template <class Cell, class Inserter>
point_t const & grid_t<Cell, Inserter>::cell_visiter_t::start_point() const
{
    return start_point_;
}

template <class Cell, class Inserter>
bool grid_t<Cell, Inserter>::cell_visiter_t::move_start_point(double x)
{
    line_t line(segment_.first, segment_.second);
    double y = line.get_y(x);
    if (y < segment_.second.y)
    {
        start_point_ = segment_.second;
        return false;
    }
    start_point_ = point_t(x, y);
    start_point_.x = (step_ > 0) ? start_point_.x + EPSILON: start_point_.x - EPSILON;
    return true;
}

template <class Cell, class Inserter>
int grid_t<Cell, Inserter>::cell_visiter_t::step() const
{
    return step_;
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::add_empty_cells()
{
    for(int i = min_idx_.first; i <= max_idx_.first; ++i)
    {
        for(int j = min_idx_.second; j <= max_idx_.second; ++j)
        {
            cell_idx_t idx(i, j);
            if(data_.find(idx) == data_.end())
            {
                Cell cell(cell_center(idx));
                data_.insert(std::make_pair(idx, cell));
            }
        }
    }
}

template <class Cell, class Inserter>
void grid_t<Cell, Inserter>::set_centers_states()
{
    cell_idx_t idx = min_idx_;
    --idx.first;

    Cell prev = Cell(cell_center(idx));
    for(int i = min_idx_.first; i <= max_idx_.first; ++i)
    {
        int begin = min_idx_.second;
        int end = max_idx_.second;
        int step = 1;
        if((i - min_idx_.first) % 2 != 0)
        {
            begin = max_idx_.second;
            end = min_idx_.second;
            step = -1;
        }
        for(int j = begin; (j <= end && step > 0) || (j >= end && step < 0); j += step)
        {
            idx = cell_idx_t(i, j);
            stdext::hash_map<cell_idx_t, Cell, cell_idx_hash>::iterator iter = data_.find(idx);
            if(iter != data_.end())
            {
                iter->second.center_in(set_center_state(iter->second, prev));
                prev = iter->second;
            }
        }
    }
}

template <class Cell, class Inserter>
bool grid_t<Cell, Inserter>::set_center_state(Cell const & current, Cell const & prev)
{
    manhattan_line_t m_line(current.center(), prev.center());

	boost::optional<segment_t const &> seg = current.min_segment(m_line, BASE_PART);
    point_pos pos_a;// = (seg) ? point_position(*seg, current.center()) : UNDEFINED;
    if(seg)
		pos_a = point_position(*seg, current.center());
	else
	{
		seg = prev.min_segment(m_line, BASE_PART);
		pos_a = (seg) ? point_position(*seg, current.center()) : UNDEFINED;
	}

    point_pos pos_b  = (prev.center_in()) ? LEFT : RIGHT;

    if( (pos_a == pos_b && pos_a != ON) || pos_a == UNDEFINED)
    {
        return prev.center_in();
    }
    if(pos_a == LEFT || pos_a == ON)
    {
        return true;
    }
    return false;
}

#endif